class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s

        # 创建二维DP数组，dp[i][j]表示s[i:j+1]是否为回文串
        dp = [[False] * n for _ in range(n)]

        # 单个字符都是回文串
        for i in range(n):
            dp[i][i] = True

        start = 0  # 最长回文子串的起始位置
        max_len = 1  # 最长回文子串的长度

        # 检查长度为2的子串
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                start = i
                max_len = 2

        # 检查长度大于2的子串
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1  # 子串的结束位置
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    if length > max_len:
                        max_len = length
                        start = i

        return s[start:start + max_len]

    def longestPalindrome_brute_force(self, s: str) -> str:
        if not s:
            return ""
        n = len(s)
        max_len = 1
        start = 0
        for i in range(n):
            for j in range(i, n):
                substr = s[i:j + 1]
                if substr == substr[::-1] and (j - i + 1) > max_len:
                    max_len = j - i + 1
                    start = i
        return s[start:start + max_len]